package medium;

import java.util.ArrayList;
import java.util.List;

/**
 * 216. 组合总和 III
 * 创建时间：2024-04-21 00:29
 */
public class 组合总和III_216 {
    /**
     * 具体解法和 {@link 组合总和_39}中一致，也有枚举法
     * 下面的方法是【选与不选】的 {@link other.背包问题.零一背包}的解法
     */
    static class Solution {
        List<List<Integer>> ans = new ArrayList<>();
        int k;
        public List<List<Integer>> combinationSum3(int k, int n) {
            this.k = k;
            dfs(0, n, new ArrayList<>());
            return ans;
        }

        void dfs(int i, int left, List<Integer> path) {
            if (left == 0 && path.size() == k) {
                ans.add(new ArrayList<>(path));
                return;
            }
            i++;
            if (i > 9 || left < 0 || path.size() > k) {
                return;
            }
            // 不选
            dfs(i, left, path);
            // 选
            path.add(i);
            dfs(i, left - i, path);
            path.remove(path.size() - 1);
        }

        public static void main(String[] args) {
            Solution s= new Solution();
            System.out.println(s.combinationSum3(3, 7));
        }

    }
}
